package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;
import LeetCode.interview._141_Linked_List_Cycle.ListNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		Rotate an array of n elements to the right by k steps.
	
	For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
	
	Note:
	Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
	
	[show hint]
	
	Related problem: Reverse Words in a String II
	
	Credits:
	Special thanks to @Freezen for adding this problem and creating all test cases.
	
题目大意

	　　给定一个n个长度的数组，将它向右旋转k个位置。  
	
解题思路
			如果允许额外分配线性空间，那么可以错位复制原有数组的元素。如果允许修改原有数组，那么可以通过三次反转
		
		数组来实现收旋转，不需要申请额外空间，并且每次反转时间为O(n)，
		
		三次反转数组：第一次反转整个数组；第二次反转数组的前K个数；第三次反转数组剩下的数
		
		例如：
		
		一维数组[1,2,3,4,5,6,7],k=3
		
		第一次反转：7,6,5,4,3,2,1
		
		第二次反转：5,6,7,4,3,2,1	  //第二次反转数组的前K个数
		
		第三次反转：5,6,7,1,2,3,4    //最终结果
		
 * @Date 2017-09-14 22：20
 */
public class _189_Rotate_Array {
   
	/**
	 * @My
	 * @param nums
	 * @param k
	 */
    public void rotate(int[] nums, int k) {
    	
    	//当k大于数组长度时，取余
    	if (k > nums.length) 	k = k % nums.length;
    	
    	//第一步：翻转整个数组
    	reverse(nums, 0, nums.length-1);
    	
    	//第二部： 翻转前k个元素
    	reverse(nums, 0, k-1);
    	
    	//第三部： 翻转剩下k个元素
    	reverse(nums, k, nums.length-1);
    }
    
    private void reverse(int[] nums, int start, int end) {
    	int l = start, r=end;
      	while (l < r) {
    		exchange(nums, l++, r--);
    	}
    }
    
    public void traverse(int[] list) {
    	for (int i : list) {
    		LogUtils.print(i);
    	}
    	LogUtils.br();
    }

    private void exchange(int[] nums, int a, int b) {
    	int t = nums[a];
    	nums[a] = nums[b];
    	nums[b] = t;
    }

	public static void main(String[] args) {
		_189_Rotate_Array obj = new _189_Rotate_Array();

				obj.rotate(
//						new int[] {1, 2, 3, 4, 5, 6, 7}, 3
						new int[] {-1}, 2
						);
	}

}
